/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package util;

import java.util.List;

/**
 *
 * @author Xuan Huy
 */
public class Util {

    /**
     * La méthode échange la position (permute) des éléments d'indices
     * <code>indice1</code> et
     * <code>indice2</code> de la liste passée en paramètre.
     *
     * @param liste une liste d'entiers.
     * @param indice1 indice d'une des deux éléments permutés.
     * @param indice2 indice d'une des deux éléments permutés.
     * @throws IndexOutOfBoundsException si <code>indice1</code>
     * et <code>indice2</code> sont invalides.
     */
    public static void echanger(List<Integer> liste, int indice1, int indice2)
            throws IndexOutOfBoundsException {
        if (indice1 < 0 || indice1 >= liste.size() || indice2 < 0
                || indice2 >= liste.size()) {
            throw new IndexOutOfBoundsException();
        }
        Integer intermediaire = liste.get(indice2);
        liste.set(indice2, liste.get(indice1));
        liste.set(indice1, intermediaire);
    }

    /**
     * La méthode partitionne la liste passée en paramètres, délimitée par
     * <code>debut</code> et
     * <code>fin</code>, en deux sous-listes en prenant le dernier élément de la
     * liste comme élément pivot. Les éléments inférieurs au pivot se trouvent à
     * gauche de celui-ci, les éléments supérieurs ou égaux au pivot se trouvent
     * à droite de celui-ci.
     *
     * @param liste une liste d'entiers.
     * @param debut indice de début.
     * @param fin indice de fin
     * @return indice finale de l'élément pivot.
     * @throws IndexOutOfBoundsException si <code>debut</code>
     * et <code>fin</code> sont invalides.
     * @throws IllegalArgumentException si <code>debut > fin</code>.
     */
    public static int partitionner(List<Integer> liste, int debut, int fin)
            throws IndexOutOfBoundsException, IllegalArgumentException {
        if (debut < 0 || debut >= liste.size() || fin < 0
                || fin >= liste.size()) {
            throw new IndexOutOfBoundsException();
        }
        if (debut > fin) {
            throw new IllegalArgumentException();
        }
        int i = debut;
        if (debut < fin) {
            Integer pivot = liste.get(fin);
            for (int j = debut; j < fin; j++) {
                if (liste.get(j).compareTo(pivot) < 0) {
                    echanger(liste, i++, j);
                }
            }
            echanger(liste, i, fin);
        }
        return i;
    }

    /**
     * La méthode sélectionne et retourne le
     * <code>rang</code>-ème plus petit élément de la liste passée en paramètre,
     * délimitée par
     * <code>debut</code> et
     * <code>fin</code>.
     *
     * @param liste une liste d'entiers.
     * @param debut indice de début.
     * @param fin indice de fin
     * @param rang le rang de l'élément sélectionné.
     * @return le <code>rang + 1</code>-ème plus petit élément de la
     * liste<code>liste</code>.
     * @throws IndexOutOfBoundsException si <code>debut</code>, <code>fin</code>
     * et <code>rang</code> sont invalides.
     * @throws IllegalArgumentException si <code>debut > fin</code>.
     */
    public static Integer selectionner(List<Integer> liste, int debut, int fin,
            int rang) throws IndexOutOfBoundsException, IllegalArgumentException {
        if (rang < 0 || rang >= liste.size()) {
            throw new IndexOutOfBoundsException();
        }
        if (debut < 0 || debut >= liste.size() || fin < 0
                || fin >= liste.size()) {
            throw new IndexOutOfBoundsException();
        }
        if (debut > fin) {
            throw new IllegalArgumentException();
        }
        if (debut == fin) {
            return liste.get(fin);
        }
        int indicePivot = partitionner(liste, debut, fin);
        int nb = indicePivot - debut + 1;
        if (rang == nb) {
            return liste.get(indicePivot);
        }
        if (rang < nb) {
            return selectionner(liste, debut, indicePivot - 1, rang);
        }
        return selectionner(liste, indicePivot + 1, fin, rang - nb);
    }
}
